package com.gyj.user.controller;

import java.util.*;

/**
 * Created by Gao on 2018/12/4.
 */
public class HashMap7<K, V> extends AbstractMap<K, V> implements Map<K, V> {

    // 默认的初始容量是16，必须是2的幂。
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    // 默认加载因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 存储数据的entry数组，长度是2的幂次方，HashMap是采用拉链法实现的，每一个Entry本质上是一个单向链表
    private transient Entry<K, V>[] table;

    // HashMap的大小，它是HashMap保存的键值对的数量
    transient int size;

    // HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）
    int threshold;

    // 加载因子实际大小
    final float loadFactor;

    // HashMap被改变的次数
    volatile int modCount;

    // HashMap的Entry对应的集合
    private Set<Map.Entry<K, V>> entrySet = null;

    /**
     * 指定容量大小和加载因子的构造函数
     */
    public HashMap7(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);

        // HashMap的最大容量只能是MAXIMUM_CAPACITY
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

        // 找出"大于initialCapacity"的最小的2的幂, 保证容量都是2的幂次方
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        // 设置加载因子
        this.loadFactor = loadFactor;
        // 设置HashMap阈值，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
        threshold = (int) (capacity * loadFactor);
        // 创建Entry数组，用来保存数据
        table = new Entry[capacity];
    }

    /**
     * 指定容量大小的构造函数
     */
    public HashMap7(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 默认构造函数
     */
    public HashMap7() {
        // 设置加载因子
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
        threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        // 创建Entry数组，用来保存数据
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
    }

    //hash函数
    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    // 返回索引值, h & (length-1)保证返回值的小于length
    static int indexFor(int h, int length) {
        return h & (length - 1);
    }

    /**
     * HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个Entry对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，
     * 当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，
     * 也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry
     *
     * @param key
     */
    @Override
    public V get(Object key) {
        if (key == null) {
            return getForNullKey();
        }
        int hash = hash(key.hashCode());
        //indexFor(hash,table.length)用来计算在table数组中存储Entry对象的精确的索引
        int i = indexFor(hash, table.length);
        Entry<K, V> entry = table[i];
        for (Entry<K, V> e = entry; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                return e.value;
            }
        }
        return null;
    }

    // 获取key为null的元素的值, HashMap将key为null的元素存储在table[0]位置
    private V getForNullKey() {
        for (Entry<K, V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

    /**
     * put方法，添加key-value
     *
     * @param key
     * @param value
     */
    @Override
    public V put(K key, V value) {

        // 若key为null，则将该键值对添加到table[0]中。
        if (key == null)
            return putForNullKey(value);

        // 若"key不为null"，则根据key的hashCode()方法计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
        //int hash = 1; //模拟hash冲突的情况
        int hashCode = key.hashCode();
        int hash = hash(hashCode);
        int i = indexFor(hash, table.length);

        //计算出来该位置，然后顺着该位置找下一个对象，也就是在链表上找
        //如果key已经存在就直接返回旧值，可以利用hashMap.put方法去重
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

        // 若该key对应的键值对不存在，则将key-value添加到table中
        modCount++;
        addEntry(hash, key, value, i);

        return null;
    }

    // putForNullKey()的作用是将key为null键值对添加到table[0]位置
    private V putForNullKey(V value) {
        for (Entry<K, V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        // 这里的完全不会被执行到!
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

    //新增Entry，将key-value插入指定位置，bucketIndex是位置索引
    private void addEntry(int hash, K key, V value, int bucketIndex) {
        //保存bucketIndex位置的元素到e中
        Entry<K, V> e = table[bucketIndex];

        //设置bucketIndex位置元素为新的Entry, 设置e为新Entry的下一个节点
        //数组table中的每一个元素都是一个Entry对象，每次添加都要new一个新的Entry
        table[bucketIndex] = new Entry<>(hash, key, value, e);

        size++;
        System.out.println("现在的size大小是: " + size);
        if (size > threshold) {
            //扩容
            resize(2 * table.length);
        }
    }

    //扩容方法
    private void resize(int newCapacity) {
        Entry<K, V>[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            //threshold = 容量*加载因子    Integer.MAX_VALUE为 0x7fffffff
            threshold = Integer.MAX_VALUE;
            return;
        }

        //参考数组的定义形式 int[] a = new int[256];
        //Entry<K, V>[] newTable = new Entry<K, V>[newCapacity]会报错
        Entry<K, V>[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int) (newCapacity * loadFactor);
    }

    //将HashMap中的全部元素都添加到newTable中
    private void transfer(Entry<K, V>[] newTable) {
        Entry<K, V>[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K, V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K, V> next = e.next;
                    //重新根据新的newTable计算散列值
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

    //entrySet是AbstractMap中的抽象方法，非抽象类继承抽象类，需要把抽象类中所有抽象方法全部实现
    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        return entrySet0();
    }

    // 返回HashMap的Entry集合，它实际是返回一个EntrySet对象
    private Set<Map.Entry<K, V>> entrySet0() {
        Set<Map.Entry<K, V>> es = entrySet;
        return es != null ? es : (entrySet = new EntrySet());
    }

    // EntrySet对应的集合, EntrySet继承于AbstractSet，说明该集合中没有重复的EntrySet。
    private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {

        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<K, V> e = (Map.Entry<K, V>) o;
            Entry<K, V> candidate = getEntry(e.getKey());
            return candidate != null && candidate.equals(e);
        }

        //这里没有实现
        public boolean remove(Object o) {
            return false;
        }

        //这个方法不能少，否则map里面存放不了数据
        @Override
        public Iterator<Map.Entry<K, V>> iterator() {
            return newEntryIterator();
        }

        public int size() {
            return size;
        }

        public void clear() {
            HashMap7.this.clear();
        }
    }

    // 返回键为key的键值对
    final Entry<K, V> getEntry(Object key) {
        // 获取哈希值, HashMap将key为null的元素存储在table[0]位置
        // key不为null的则调用hash()计算哈希值
        int hash = (key == null) ? 0 : hash(key.hashCode());
        // 在该hash值对应的链表上查找键值等于key的元素
        int i = indexFor(hash, table.length);
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

    // 返回一个Entry迭代器
    Iterator<Map.Entry<K, V>> newEntryIterator() {
        return new EntryIterator();
    }

    // Entry的迭代器
    private final class EntryIterator extends HashIterator<Map.Entry<K, V>> {
        public Map.Entry<K, V> next() {
            return nextEntry();
        }
    }

    // HashIterator是HashMap迭代器的抽象出来的父类，实现了公共了函数。
    // 它包含key迭代器(KeyIterator)、Value迭代器(ValueIterator)和
    // Entry迭代器(EntryIterator)3个子类。
    private abstract class HashIterator<E> implements Iterator<E> {
        Entry<K, V> next;    //下一个元素
        int expectedModCount;   //expectedModCount用于实现fast-fail机制。
        int index;   // 当前索引
        Entry<K, V> current;  //当前元素

        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) {
                Entry[] t = table;
                // 将next指向table中第一个不为null的元素。
                // 这里利用了index的初始值为0，从0开始依次向后遍历，直到找到不为null的元素就退出循环。
                while (index < t.length && (next = t[index++]) == null) ;
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

        // 获取下一个元素
        final Entry<K, V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K, V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            /**
             * 注意！！！
             * 一个Entry就是一个单向链表, 若该Entry的下一个节点不为空，
             * 就将next指向下一个节点; 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。
             */
            if ((next = e.next) == null) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null) ;
            }
            current = e;
            return e;
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }

    @Override
    public boolean containsValue(Object value) {
        if (value == null) {
            return containsNullValue();
        }
        // 若value不为null，则查找HashMap中是否有值为value的节点。
        Entry[] tab = table;
        for (Entry aTab : tab)
            for (Entry e = aTab; e != null; e = e.next)
                if (value.equals(e.value))
                    return true;
        return false;
    }

    // 是否包含null值
    private boolean containsNullValue() {
        Entry<K, V>[] tab = table;
        for (Entry<K, V> aTab : tab)
            for (Entry e = aTab; e != null; e = e.next)
                if (e.value == null)
                    return true;
        return false;
    }

    @Override
    public V remove(Object key) {
        return null;
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {

    }

    @Override
    // 清空HashMap，将所有的元素设为null
    public void clear() {
        modCount++;
        Entry[] tab = table;
        for (int i = 0; i < tab.length; i++)
            tab[i] = null;
        size = 0;
    }

    @Override
    public Set<K> keySet() {
        return null;
    }

    @Override
    public Collection<V> values() {
        return null;
    }

    // 静态内部类，Entry是单向链表, 它是HashMap链式存储法对应的链表。
    // 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value),
    // equals(Object o), hashCode()这些函数
    static class Entry<K, V> implements Map.Entry<K, V> {
        final K key;
        V value;
        Entry<K, V> next;
        final int hash;

        Entry(int hash, K key, V value, Entry<K, V> next) {
            this.hash = hash;
            this.value = value;
            this.next = next;
            this.key = key;
        }

        @Override
        public final K getKey() {
            return key;
        }

        @Override
        public final V getValue() {
            return value;
        }

        @Override
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
    }

    /**
     * 以下是测试例子
     */
    private static void test1() {
        HashMap7<String, String> map = new HashMap7<>();
        map.put("1", "111");
        map.put("1", "222");
        Iterator iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator.next();
            System.out.println("next : " + entry.getKey() + " - " + entry.getValue());
        }
        for (Map.Entry<String, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + "--" + entry.getValue());
        }
        System.out.println("size:" + map.size());
        System.out.println(map.get("1"));
        map.containsKey("11");
        System.out.println("contains key two : " + map.containsKey("1"));
        map.containsValue("222");
    }

    private static void test2() {
        HashMap7<Integer, Integer> map = new HashMap7<>();
        for (int i = 0; i < 200; i++) {
            //测试hash冲突
            if (i % 16 == 1) {
                map.put(i, i);
            }
        }

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + "--" + entry.getValue());
        }
    }

    public static void main(String[] args) {
        //test1();
        test2();
    }
}
